#include "../Basics/BasicStruct.cpp"

//输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

ListNode* MergeSortListTail(ListNode* l1, ListNode* l2) {
    ListNode* p = l1;
    ListNode* q = l2;
    ListNode* pos = (ListNode*) malloc(sizeof (ListNode));
    pos->next = NULL;
    ListNode* head = pos;
    while (p!=NULL && q!= NULL) {
        if (p->data > q->data) {
            pos->next = q;
            pos = pos->next;
            q = q->next;
        }else {
            pos->next = p;
            pos = pos->next;
            p = p->next;
        }
    }

    if (p != NULL) {
        pos->next = p;
    }
    if (q != NULL) {
        pos->next = q;
    }
    return head->next;
}

ListNode* MergeSortListHead(ListNode* l1, ListNode* l2) {
    ListNode* p = l1;
    ListNode* q = l2;
    ListNode* head = (ListNode*) malloc(sizeof(ListNode));
    head->next = NULL;
    while (p!=NULL && q!= NULL) {
        if (p->data > q->data) {
            ListNode* node = p->next;
            p->next = head->next;
            head->next = p;
            p = node;
        }else {
            ListNode* node = q->next;
            q->next = head->next;
            head->next = q;
            q = node;
        }
    }

        while(p != NULL) {
            ListNode* temp= p->next;
            p->next = head->next;
            head->next = p;
            p = temp;
        }

        while(q != NULL) {
            ListNode* temp= q->next;
            q->next = head->next;
            head->next = q;
            q = temp;
        }
    return head->next;
}


int main() {
    ListNode* A = CreateList();
    ListNode* B = CreateList();
    ListNode* p = MergeSortListHead(A,B);
    PrintList(p);
}